home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / linklist / source.lha / sorted.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-08  |  7.8 KB  |  271 lines
  1. #include    <stdio.h>
  2. #include    <string.h>
  3. #include    "list.h"
  4.  
  5. static void    addPersonSorted(), addPerson();
  6. static int    fndNxtPerson(), sortPerson(), compare();
  7.  
  8. typedef struct person {
  9.     char    lastname[15];
  10.     char    firstname[15];
  11. } Person, *PersonPtr;
  12. int    personSz = sizeof(Person);
  13.  
  14. main()
  15. {
  16.     Person    person;
  17.     int    id, code;
  18.  
  19. /* ------- first solution --------------------------------------------------- */
  20. fprintf(stdout, "..... Insert sorted by last name .....\n");
  21.     id = lDef(lSINGLY, lCHAIN);
  22.     addPersonSorted(id, "Ernie", "Makris");
  23.     addPersonSorted(id, "Anita", "Eijs");
  24.     addPersonSorted(id, "John", "Johnson");
  25.     addPersonSorted(id, "Bart", "Simpson");
  26.     addPersonSorted(id, "James", "Bond");
  27.     addPersonSorted(id, "Al", "Bundy");
  28.  
  29.     code = lGetNode(id, lFIRST, &person, personSz);
  30.     while (code != lEOL && code != lEMPTY_LIST) {
  31.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  32.         code = lGetNode(id, lNEXT, &person, personSz);
  33.     }
  34.     code = lDel(id);
  35.  
  36. /* ------- second solution -------------------------------------------------- */
  37. fprintf(stdout, "..... Insert unsorted .....\n");
  38.     id = lDef(lSINGLY, lCHAIN);
  39.     addPerson(id, "Ernie", "Makris");
  40.     addPerson(id, "Anita", "Eijs");
  41.     addPerson(id, "John", "Johnson");
  42.     addPerson(id, "Bart", "Simpson");
  43.     addPerson(id, "James", "Bond");
  44.     addPerson(id, "Al", "Bundy");
  45.  
  46.     code = lGetNode(id, lFIRST, &person, personSz);
  47.     while (code != lEOL && code != lEMPTY_LIST) {
  48.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  49.         code = lGetNode(id, lNEXT, &person, personSz);
  50.     }
  51.  
  52. fprintf(stdout, "..... Sort by last name .....\n");
  53.     id = sortPerson(id);
  54.  
  55.     code = lGetNode(id, lFIRST, &person, personSz);
  56.     while (code != lEOL && code != lEMPTY_LIST) {
  57.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  58.         code = lGetNode(id, lNEXT, &person, personSz);
  59.     }
  60.  
  61.     code = lDel(id);
  62.  
  63. /* ------- third solution --------------------------------------------------- */
  64. fprintf(stdout, "..... Insert unsorted .....\n");
  65.     id = lDef(lSINGLY, lCHAIN);
  66.     addPerson(id, "Ernie", "Makris");
  67.     addPerson(id, "Anita", "Eijs");
  68.     addPerson(id, "John", "Johnson");
  69.     addPerson(id, "Bart", "Simpson");
  70.     addPerson(id, "James", "Bond");
  71.     addPerson(id, "Al", "Bundy");
  72.  
  73.     code = lGetNode(id, lFIRST, &person, personSz);
  74.     while (code != lEOL && code != lEMPTY_LIST) {
  75.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  76.         code = lGetNode(id, lNEXT, &person, personSz);
  77.     }
  78.  
  79. fprintf(stdout, "..... Sort by last name ..... Bubble ASCENDING .....\n");
  80.     code = lSort(id, lASCENDING, lBUBBLE, compare);
  81.  
  82.     code = lGetNode(id, lFIRST, &person, personSz);
  83.     while (code != lEOL && code != lEMPTY_LIST) {
  84.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  85.         code = lGetNode(id, lNEXT, &person, personSz);
  86.     }
  87.  
  88. fprintf(stdout, "..... Sort by last name ..... Bubble DESCENDING .....\n");
  89.     code = lSort(id, lDESCENDING, lBUBBLE, compare);
  90.  
  91.     code = lGetNode(id, lFIRST, &person, personSz);
  92.     while (code != lEOL && code != lEMPTY_LIST) {
  93.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  94.         code = lGetNode(id, lNEXT, &person, personSz);
  95.     }
  96.  
  97. fprintf(stdout, "..... Sort by last name ..... Heap ASCENDING .....\n");
  98.     code = lSort(id, lASCENDING, lHEAP, compare);
  99.  
  100.     code = lGetNode(id, lFIRST, &person, personSz);
  101.     while (code != lEOL && code != lEMPTY_LIST) {
  102.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  103.         code = lGetNode(id, lNEXT, &person, personSz);
  104.     }
  105.  
  106. fprintf(stdout, "..... Sort by last name ..... Heap DESCENDING .....\n");
  107.     code = lSort(id, lDESCENDING, lHEAP, compare);
  108.  
  109.     code = lGetNode(id, lFIRST, &person, personSz);
  110.     while (code != lEOL && code != lEMPTY_LIST) {
  111.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  112.         code = lGetNode(id, lNEXT, &person, personSz);
  113.     }
  114.  
  115. fprintf(stdout, "..... Sort by last name ..... Insert ASCENDING .....\n");
  116.     code = lSort(id, lASCENDING, lINSERT, compare);
  117.  
  118.     code = lGetNode(id, lFIRST, &person, personSz);
  119.     while (code != lEOL && code != lEMPTY_LIST) {
  120.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  121.         code = lGetNode(id, lNEXT, &person, personSz);
  122.     }
  123.  
  124. fprintf(stdout, "..... Sort by last name ..... Insert DESCENDING .....\n");
  125.     code = lSort(id, lDESCENDING, lINSERT, compare);
  126.  
  127.     code = lGetNode(id, lFIRST, &person, personSz);
  128.     while (code != lEOL && code != lEMPTY_LIST) {
  129.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  130.         code = lGetNode(id, lNEXT, &person, personSz);
  131.     }
  132.  
  133. fprintf(stdout, "..... Sort by last name ..... Quick ASCENDING .....\n");
  134.     code = lSort(id, lASCENDING, lQUICK, compare);
  135.  
  136.     code = lGetNode(id, lFIRST, &person, personSz);
  137.     while (code != lEOL && code != lEMPTY_LIST) {
  138.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  139.         code = lGetNode(id, lNEXT, &person, personSz);
  140.     }
  141.  
  142. fprintf(stdout, "..... Sort by last name ..... Quick DESCENDING .....\n");
  143.     code = lSort(id, lDESCENDING, lQUICK, compare);
  144.  
  145.     code = lGetNode(id, lFIRST, &person, personSz);
  146.     while (code != lEOL && code != lEMPTY_LIST) {
  147.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  148.         code = lGetNode(id, lNEXT, &person, personSz);
  149.     }
  150.  
  151. fprintf(stdout, "..... Sort by last name ..... Selection ASCENDING .....\n");
  152.     code = lSort(id, lASCENDING, lSELECTION, compare);
  153.  
  154.     code = lGetNode(id, lFIRST, &person, personSz);
  155.     while (code != lEOL && code != lEMPTY_LIST) {
  156.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  157.         code = lGetNode(id, lNEXT, &person, personSz);
  158.     }
  159.  
  160. fprintf(stdout, "..... Sort by last name ..... Selection DESCENDING .....\n");
  161.     code = lSort(id, lDESCENDING, lSELECTION, compare);
  162.  
  163.     code = lGetNode(id, lFIRST, &person, personSz);
  164.     while (code != lEOL && code != lEMPTY_LIST) {
  165.         fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  166.         code = lGetNode(id, lNEXT, &person, personSz);
  167.     }
  168.  
  169.     code = lDel(id);
  170. }
  171.  
  172. static void
  173. addPersonSorted(id, first, last)
  174. int    id;
  175. char    *first, *last;
  176. {
  177.     Person    person, new;
  178.     char    tmp[15];
  179.     int    code;
  180.  
  181.         /* find next last name */
  182.     strcpy(&tmp[0], last);
  183.     code = lFndNode(id, lFIRST, fndNxtPerson, &tmp[0], &person, personSz);
  184.  
  185.     strcpy(new.lastname, last);
  186.     strcpy(new.firstname, first);
  187.  
  188.         /* insert data in alphabetical order */
  189.     if (code == lEMPTY_LIST || code == lFIRST)
  190.         code = lInsNode(id, lFIRST, &new, personSz, 0);
  191.     else if (code == lNOT_FOUND)
  192.         code = lInsNode(id, lLAST, &new, personSz, 0);
  193.     else
  194.         code = lInsNode(id, lBEFORE, &new, personSz, 0);
  195. }
  196.  
  197. /* find next by specified last name before which specified name must be */
  198. /* inserted (alphabetical order) */
  199. static int
  200. compare(p1, p2, order)
  201. PersonPtr    p1, p2;
  202. int        order;
  203. {
  204.     int    k = strcmp(p1->lastname, p2->lastname);
  205.  
  206.     if (k == 0)
  207.         return(lSAME);
  208.     else if (k > 0)
  209.         return(l2LT1);
  210.     else if (k < 0)
  211.         return(l1LT2);
  212. }
  213.  
  214. /* find next by specified last name before which specified name must be */
  215. /* inserted (alphabetical order) */
  216. static int
  217. fndNxtPerson(last, data)
  218. char        *last;
  219. PersonPtr    data;
  220. {
  221.     if (strcmp(last, data->lastname) < 0)
  222.         return(lFOUND);
  223.     else
  224.         return(lNOT_FOUND);
  225. }
  226.  
  227. static void
  228. addPerson(id, first, last)
  229. int    id;
  230. char    *first, *last;
  231. {
  232.     Person    new;
  233.     int    code;
  234.  
  235.     strcpy(new.lastname, last);
  236.     strcpy(new.firstname, first);
  237.     code = lInsNode(id, lLAST, &new, personSz, 0);
  238. }
  239.  
  240. static int
  241. sortPerson(id)
  242. int    id;
  243. {
  244.     Person    person, next;
  245.     char    tmp[15];
  246.     int    code, id2;
  247.  
  248.     id2 = lDef(lSINGLY, lCHAIN);
  249.  
  250.     code = lGetNode(id, lFIRST, &person, personSz);
  251.     while (code != lEOL && code != lEMPTY_LIST) {
  252.  
  253.             /* find next last name */
  254.         strcpy(&tmp[0], person.lastname);
  255.         code = lFndNode(id2, lFIRST, fndNxtPerson, &tmp[0], &next,
  256.             personSz);
  257.  
  258.             /* insert data in alphabetical order */
  259.         if (code == lEMPTY_LIST || code == lFIRST)
  260.             code = lInsNode(id2, lFIRST, &person, personSz, 0);
  261.         else if (code == lNOT_FOUND)
  262.             code = lInsNode(id2, lLAST, &person, personSz, 0);
  263.         else
  264.             code = lInsNode(id2, lBEFORE, &person, personSz, 0);
  265.  
  266.         code = lGetNode(id, lNEXT, &person, personSz);
  267.     }
  268.     code = lDel(id);
  269.     return(id2);
  270. }
  271.